// 共享栈：两个栈共享一个数组的储存空间
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 1000

/**
 * 第一个栈从头部开始存放元素，第二个栈从尾部开始储存元素
 * 第一个栈的头指针是top1，初始位于下标-1，每压入一个元素top1++
 * 第二个栈的头指针是top2，初始位于下标MAX_SIZE，每压入一个元素top2--
 * 两个头指针总是指着两个栈的顶部元素
 * 当top1 + 1 = top2时栈满
 */
/// @brief 共享栈，即两个栈共用一个数组空间
typedef struct
{
	char storage[MAX_SIZE];
	int top1;
	int top2;
} ShareStack;

/// @brief 创建一个共享栈
/// @return 共享栈对象指针
ShareStack *createShareStack()
{
	ShareStack *stack = (ShareStack *)malloc(sizeof(ShareStack));
	stack->top1 = -1;
	stack->top2 = MAX_SIZE;
	return stack;
}

/// @brief 判断共享栈是否已满
/// @param stack 共享栈对象指针
/// @return 共享栈是否满
int shareStackFull(ShareStack *stack)
{
	return stack->top1 + 1 == stack->top2;
}

/// @brief 判断共享栈中某个栈是否为空
/// @param stack 共享栈对象指针
/// @param flag 为1时判断第一个栈，为2时判断第二个栈
/// @return 是否为空
int shareStackEmpty(ShareStack *stack, int flag)
{
	return (flag == 1 && stack->top1 == -1) || (flag == 2 && stack->top2 == MAX_SIZE);
}

/// @brief 向共享栈压入元素
/// @param stack 共享栈对象指针
/// @param flag 当为1时压入第一个栈，为2则压入第二个栈
/// @param data 压入的元素
void push(ShareStack *stack, int flag, char data)
{
	// 满则不进行操作
	if (shareStackFull(stack))
	{
		return;
	}
	if (flag == 1)
	{
		stack->storage[++stack->top1] = data;
	}
	else if (flag == 2)
	{
		stack->storage[--stack->top2] = data;
	}
}

/// @brief 从共享栈弹出元素
/// @param stack 共享栈对象指针
/// @param flag 当为1时弹出第一个栈的元素，为2则弹出第二个栈的元素
/// @return 弹出的元素
char pop(ShareStack *stack, int flag)
{
	// 为空则返回0
	if (shareStackEmpty(stack, flag))
	{
		return 0;
	}
	if (flag == 1)
	{
		return stack->storage[stack->top1--];
	}
	if (flag == 2)
	{
		return stack->storage[stack->top2++];
	}
}

int main()
{
	ShareStack *stack = createShareStack();
	push(stack, 1, 'A');
	push(stack, 1, 'B');
	push(stack, 1, 'C');
	push(stack, 2, 'X');
	push(stack, 2, 'Y');
	push(stack, 2, 'Z');
	printf("%c", pop(stack, 1));
	printf("%c", pop(stack, 1));
	printf("%c", pop(stack, 2));
	return 0;
}